package 力扣91;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName : Day_17_297_二叉树的序列化与反序列化
 * @Author : 骆发茂
 * @Date: 2021/12/28 9:58
 * @Description : https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/297-er-cha-shu-de-xu-lie-hua-yu-fan-xu-l-647c/
 */
public class Day_17_297_二叉树的序列化与反序列化_BFS {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */

    /**
     * 思路一：BFS
     * 序列化
     * 用BFS遍历树，与一般遍历的不同点是不管node的左右子节点是否存在，统统加到队列中
     * 在节点出队时，如果节点不存在，在返回值res中加入一个”null“；如果节点存在，则加入节点值的字符串形式
     * 反序列化
     * 同样使用BFS方法，利用队列新建二叉树
     * 首先要将data转换成列表，然后遍历，只要不为null将节点按顺序加入二叉树中；同时还要将节点入队
     * 队列为空时遍历完毕，返回根节点
     * <p>
     * 作者：edelweisskoko
     * 链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/solution/297-er-cha-shu-de-xu-lie-hua-yu-fan-xu-l-647c/
     */
    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            StringBuilder res = new StringBuilder();
            res.append("[");
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {

                TreeNode node = queue.poll();//取出并删除
                if (node != null) {
                    res.append("" + node.val);
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    res.append("null");
                }
                res.append(",");

            }
            res.append("]");
            return res.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == "") {
                return null;
            }
            String[] datalist = data.substring(1, data.length() - 1).split(",");
            TreeNode root = new TreeNode(Integer.parseInt(datalist[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (!"null".equals(datalist[i])) {
                    node.left = new TreeNode(Integer.parseInt(datalist[i]));
                    queue.offer(node.left);
                }
                i++;
                if (!"null".equals(datalist[i])) {
                    node.right = new TreeNode(Integer.parseInt(datalist[i]));
                    queue.offer(node.right);
                }
                i++;

            }
            return root;

        }
    }

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
}